﻿//Write a program that finds all prime numbers in the range [1...10 000 000]. Use the sieve of Eratosthenes algorithm (find it in Wikipedia).

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _15SieveOfEratosthenesAlgoPrimeNums
{
    class Program
    {
        static void Main(string[] args)
        {
            bool[] array = new bool[(int)1E7];  // (int)1E7 = 10 000 000.
            int p = 2;
            for (int i = 2; i < Math.Sqrt(array.Length); i++)
            {
                if (array[i] == false)
                {
                    for (int j = i * i; j < array.Length; j=j+i)
                    {
                        array[j] = true;
                    }
                }
            }
            for (int i = 2; i < array.Length; i++)
            {
                if (array[i] == false)
                {
                    Console.Write(i + " ");
                }
            }
            
        }
    }
}
